package com.leetcode.partition1;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/20 17:25
 */
public class LC97交错字符串 {

    public static boolean isInterleave(String s1, String s2, String s3) {
        //边界判断
        if (s3.length() == 0) return s1.length() == 0 && s2.length() == 0;
        if (s1.length() + s2.length() != s3.length()) return false;
        if (s1.length() == 0 && s2.length() != 0) return s2.equals(s3);
        if (s2.length() == 0 && s1.length() != 0) return s1.equals(s3);
        return dynamicProgramming(s1, s2, s3);
    }

    private static boolean dynamicProgramming(String s1, String s2, String s3) {
        //问题转化类似于力扣63题不同路径。s1为左边墙壁，s2为横向墙壁，是否存在一条s3的路径到达右下方。路径每个字符都是从s1向下和s2向右得到的
        //dp[i][j]：字符串s1[0, i)和字符串s2[0, j)能否组成s3[0, i + j)，也就是是否存在一条s3[0, i + j)的路径
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;
        //s1不为空，s2位空时，需要s1和s3对应匹配；s2不为空，s1为空，需要s2和s3对应匹配
        for (int i = 1; i <= s1.length() && s1.charAt(i - 1) == s3.charAt(i - 1); i++) dp[i][0] = true;
        for (int j = 1; j <= s2.length() && s2.charAt(j - 1) == s3.charAt(j - 1); j++) dp[0][j] = true;
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                //k为s3最后一位的索引
                int k = i + j - 1;
                //对于dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(k)来说，当前位置要想可达，则需要上一个位置可达，也就是dp[i-1][j]，同时
                //还需要当前的道路能连通，也就是s1.charAt(i-1)==s3.charAt(k)；对于dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(k)同理
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(k)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(k));
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return dp[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        String s1 = "aa", s2 = "ab", s3 = "abaa";
        System.out.println(isInterleave(s1, s2, s3));
    }
}
